// https://leetcode-cn.com/problems/subsets/submissions/

class Solution {
public:
    void helper(vector<int>& nums, vector<int>& tmp, vector<vector<int>>& res, int start) {
        // if (start >= nums.size()) {
            res.push_back(tmp);
            // return;
        // }; 此题非常特殊，所有路径都应该加入结果集，所以不存在结束条件。或者说当 start 参数越过数组边界的时候，程序就自己跳过下一层递归了
        for (int i = start; i < nums.size(); ++i) {
            tmp.push_back(nums[i]);
            // helper(nums, tmp, res, start + 1); 注意！！！
            helper(nums, tmp, res, i + 1);
            tmp.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        helper(nums, tmp, res, 0);
        return res;
    }
};

// 法二：二进制表示是否放入子集
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        for (int mask = 0; mask < (1 << n); ++mask) {
            vector<int> tmp;
            for (int i = 0; i < n; ++i) {
                if (mask & (1 << i)) {
                    tmp.push_back(nums[i]);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};